class Solution {

    Map<Character, String> map = new HashMap<Character, String>() {{
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};

    public List<String> letterCombinations(String digits) {

        List<String> res = new LinkedList<>();
        int n = digits.length();
        if (n == 0) {
            return res;
        }
        StringBuilder path =  new StringBuilder(n);
        dfs(digits, 0, path, res);
        return res;
    }

    public void dfs(String digits, int depth, StringBuilder path, List<String> res) {
        if (depth == digits.length()) {
            res.add(path.toString());
            return;
        }

        for (char c : map.get(digits.charAt(depth)).toCharArray()) {
            path.append(c);
            dfs(digits, depth+1, path, res);
            path.deleteCharAt(depth);
        }
    }
}